/*
    Author: Christopher Diggins
    License: MIT Licence 1.0
    Website: http://www.heron-language.com
*/

#ifndef LLSCHEME_OPTIMIZATION_HPP
#define LLSCHEME_OPTIMIZATION_HPP

namespace lls
{
	void ReplaceWithCombinators(SExpr* x) {
		// The bin_rec combinator is an important one.
		// How do I find it? Well a function returns an s-expression that calls itself 
		// twice. We would expect how
		// So we look for an "apply" with the same argument, in two separate branches. 
		// But how do we write the combination? Well that is tricky.
		// I should not worry about it, until it becomes a big deal.
		// [...] leftargs1 rightargs2 combineif  
	}

	void GetFormalArgNames(Formals* x, Strings& args) {
		for (int i=0; i < x->GetNumChildren(); ++i) {
			args.Push(x->GetFormal(i)->GetNameStr());
		}
	}
	
	void GetVarNames(Seq* x, Strings& vars) {
		for (int i=0; i < x->GetNumChildren(); ++i) {
			if (x->GetChild(i)->Is<Var>()) {
				Var* var = x->GetChild(i)->As<Var>();
				vars.Push(var->GetNameStr());
			}
		}
	}
	
	struct GetModifiedVars {
		Strings& vars;
		GetModifiedVars(Strings& xs) 
			: vars(xs)
		{ }

		void operator()(SExpr* x) {
			if (x->Is<Set>()) {
				vars.Push(x->As<Set>()->GetNameStr());
			}
			else if (x->Is<Invoke>()) {
				// TODO:
			}
		}
	};

	void RemoveImplicitScopes(SExpr* x) {
 		x->ForEach(RemoveImplicitScopes);
		if (x->Is<Lambda>()) {
			Lambda* y = x->As<Lambda>();
			Strings names;
			GetFormalArgNames(y->GetFormals(), names);			
			for (int i=names.Count()-1; i >= 0; --i) {
				y->Body()->AddChild(new Undeclare(names[i]));
			}
		}
		else if (x->Is<Define>()) {
			Define* y = x->As<Define>();
			Strings names;
			GetFormalArgNames(y->GetFormals(), names);
			for (int i=names.Count()-1; i >= 0; --i) {
				y->Body()->AddChild(new Undeclare(names[i]));
			}
		}
		else if (x->Is<Seq>()) {
			Seq* y = x->As<Seq>();
			Strings names;
			GetVarNames(y, names);
			for (int i=names.Count()-1; i >= 0; --i) {
				y->AddChild(new Undeclare(names[i]));
			}
		}
	}

	void ReplaceSetWithNewVar(SExpr* x) {
	}

	// Rewrite anything that looks like: 
	//    setat(x i (f (getat x i))) 
	// into 
	//   applyat(x i (lambda ($1) (f($1))) // -1 byte for getat, -1 byte for getN[x], maybe more for "i"
	// This way, we can generalize it over the collection.
	// In other wrords: transform it into a map.
	void ComputeTransforms(SExpr* x) {
		/*
		if (x->Is<SetAt>()) {
			if (Has<GetAt>(x->AsSet)) {
				// TODO:
			}
		}
		x->ForEach(ComputeTransforms);
		*/
	}

	void RewriteForAsForEach(SExpr* x) {
		// TODO:
	}

	void LiftCountOutOfLoop(SExpr* x) {
		// TODO: 
		// analyzes whether lifting a "count" out of a loop can be done without changing the value.
	}

	void RewriteForEachAsForEachIndex(SExpr* x) {
		// TODO:
	}

	void RewriteForEachIndexAsMap(SExpr* x) {
		// TODO:
	}

	void RemoveUnusedVars(SExpr* x) {
		// TODO:
	}

	bool IsUndeclaration(SExpr* x, ConstString s) {
		if (!x->Is<Undeclare>()) return false;
		return x->As<Undeclare>()->GetNameStr() == s;
	}

	SExpr* FindLastUsageAfter(SExpr* x, int n, ConstString s) {
		SExpr* r = NULL;
		for (int i=n; i < x->GetNumChildren(); ++i) {
			if (IsUndeclaration(x->GetChild(i), s))
				return r;
			// TODO: finish
		}
		return r;
	}

	/* This function is supposed to remove the need for undeclares 
		in trivial contexts where the variable is last used in a 
		simple context. This has the benefit of removing the need for 
		a pop, and reduces stack bloat. AFAICT there is no downside, 
		except that Final (which translates to "DigN") is not very efficient
		if implemented naively.

		CURRENTLY NOT SUPPORTED.
		A problem exists here because, using this before name removal seriously complicates
		name removal. Making it very hard to debug and understand the name removal 
		algorithm.
	void MarkFinals(SExpr* x) {
		Error("not currently supported");
		if (x->Is<Seq>()) {
			for (int i=0; i < x->GetNumChildren(); ++i) {
				SExpr* child = x->GetChild(i);
				if (child->Is<Var>()) {
					String s = child->As<Var>()->GetNameStr();
					VarAnalyzer va(s);
					va(x);
					Assert(va.bSimpleContext = true); 
					if (va.lastSimpleUsage != NULL) {
						va.undef->DeleteSelf();						
						va.undef = NULL;
						Replace(va.lastSimpleUsage, new Final(s));
						va.lastSimpleUsage = NULL;
					}
				}
			}
		}
		x->ForEach(MarkFinals);
	}
	*/

	struct RenameVars {
		String from;
		String to;
		RenameVars(ConstString _from, ConstString _to) 
			: from(_from), to(_to)
		{ }

		void operator()(SExpr* x) {
			if (IsAtom(x, from)) {
				x->As<Atom>()->data = to;
			}
			x->ForEach(*this);
		}
	};

	void UniquelyNameVarsFromList(SExpr* x, Strings& vars) {
		for (int i=0; i < vars.Count(); ++i) {
			String oldvar = vars[i];
			String newvar = GenSym(oldvar);
			RenameVars renamer(oldvar, newvar);
			x->ForEach(renamer);
		}
	}

	void UniquelyNameVars(SExpr* x) {
		Strings vars;
		
		if (x->Is<Seq>()) {
			GetVarNames(x->As<Seq>(), vars);
			UniquelyNameVarsFromList(x, vars);
		}
		else if (x->Is<Lambda>()) {
			GetFormalArgNames(x->As<Lambda>()->GetFormals(), vars);
			UniquelyNameVarsFromList(x, vars);
		}
		else if (x->Is<Define>()) {
			GetFormalArgNames(x->As<Define>()->GetFormals(), vars);
			UniquelyNameVarsFromList(x, vars);
		}
		else if (x->Is<For>()) {
			String index = x->As<For>()->GetNameStr();
			RenameVars(index, GenSym(index))(x);
		}
		else if (x->Is<ForEach>()) {
			String index = x->As<ForEach>()->GetNameStr();
			RenameVars(index, GenSym(index))(x);			
		}

		x->ForEach(UniquelyNameVars);
	}

	int CountVarUsage(SExpr* x, ConstString var) {
		int r = 0;
		for (int i=0; i < x->GetNumChildren(); ++i) {
			if (IsAtom(x, var)) 
				r += 1;
			r += CountVarUsage(x, var);
		}		
		return r;
	}

	void SSAConversion(SExpr* x) {
		// TODO:
	}

	void ConvertListOperations(SExpr* x) {
		// TODO: convert "get_at", "set_at", "count", "append", etc. operations.
	}

	bool CanSafelyMove(Seq* x, SExpr* from, SExpr* to) {
		Strings modvars;
		bool pastFrom = false;
		
		for (int i=0; i < x->GetNumChildren(); ++i) {
			// Note we are only looking at a subrange of "x".
			if (ContainsPtr(x, from))
				pastFrom = true;
			if (pastFrom) {
				GetModifiedVars gmv(modvars);
				gmv(x);
			}
			ContainsPtr(x, to);
				break;
		}
		for (int i=0; i < modvars.Count(); ++i) {
			if (ContainsName(from, modvars[i])) 
				return false;
		}
		// TODO: this could be inlined first. 
		// TODO: check for side effects
		// TODO: look at function modification stuff.
		// TODO: 
		if (ContainsType<Apply>(from)) {
			return false;
		}

		// TODO: verify list constsness 

		return true;
	}

	void ForwardCopyPropagation(SExpr* x) {
		if (x->Is<Seq>()) {
			Seq* seq = x->As<Seq>();
			Strings vars;
			GetVarNames(seq, vars);
			for (int i=0; i < vars.Count(); ++i) {
				String var = vars[i];				
				VarAnalyzer a(var);
				a(seq);				
				
				/*
				if (a.uses.size() == 0) {
					a.RemoveVar();
				}
				else if (a.uses.size() == 1 && a.canForwardCopy) {
					// TODO:
					// a.FirstUse()->ReplaceSelf(a.def->Expr()->Clone());
					a.RemoveVar();
				}*/
			}
		}
		x->ForEach(ForwardCopyPropagation);
	}
	
	void CommonSubexpressionElimination(SExpr* x) {
	}

	SExpr* MakeInlinedCopy(SExpr* x) {
		return NULL;
	}

	void LambdaLifting() {
	}
}

#endif
